# -*- coding: utf-8 -*-

import math
import sys

class MergeSort:
        """
                Classe MergeSort
                Parâmetros de entrada:
                        A: Lista a ser ordenada
        """
        def __init__(self, A):
                self.A = A
                self.p = 0
                self.r = len(A) - 1
                self.merge_sort(self.p, self.r)

        def merge(self, p, q, r):
                """
                        Método para ordenar as duas tabelas previamente criadas pelo método merge_sort
                """
                n1 = q - p + 1
                n2 = r - q
                L =  [0 for k in range(0, n1 + 1)]
                R = [0 for k  in range(0, n2 + 1)]
                for k in range(0, n1):
                        L[k] = self.A[p + k]
                for k in range(0, n2):
                        R[k] = self.A[q + k + 1]

                L[n1] = sys.maxint
                R[n2] = sys.maxint

                i, j = 0, 0

                for k in range(p, r + 1):
                        if L[i] <= R[j]:
                                self.A[k] = L[i]
                                i += 1
                        else:
                                self.A[k] = R[j]
                                j += 1

        def merge_sort(self, p, r):
                """
                        Método que divide a lista em duas tabelas e que no fim as ordena
                """
                if p < r:
                        q = int((p + r) / 2)
                        self.merge_sort(p, q)
                        self.merge_sort(q + 1, r)
                        self.merge(p, q, r)